package linkedlistdemo;

/**
 * @Author 12629
 * @Date 2022/3/12 12:18
 * @Description：
 */
public class TestDemo {

    /**
     * 求两个链表的相交的节点
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) {
            return null;
        }
        ListNode pl = headA;//pl指向长的链表
        ListNode ps = headB;//ps指向短的链表
        //1、分别求长度
        int lenA = 0;
        int lenB = 0;
        while (pl != null) {
            lenA++;
            pl = pl.next;
        }

        while (ps != null) {
            lenB++;
            ps = ps.next;
        }
        //需要重新修改指向
        pl = headA;
        ps = headB;

        //2、已经知道两个链表的长度了
        int len = lenA-lenB;
        if(len < 0) {
            pl = headB;
            ps = headA;
            len = lenB - lenA;
        }
        //1、求长度    2、pl永远指向 最长的那个链表   ps永远指向最短的那个链表

        //3、就是让最长的链表走len步
        while (len != 0) {
            pl = pl.next;
            len--;
        }

        //4、一人一步走 直到相遇
        while (pl != ps) {
            pl = pl.next;
            ps = ps.next;
        }

        //5、是不是两个都是null-》没有相交
        if(pl == null) {
            return null;
        }
        return pl;
    }


    public static void main(String[] args) {
        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
        singleLinkedList1.addLast(1);
        singleLinkedList1.addLast(2);
        singleLinkedList1.addLast(3);
        singleLinkedList1.addLast(4);
        singleLinkedList1.myToString();

        singleLinkedList1.printList2();
        //System.out.println(singleLinkedList1.chkPalindrome());
    }

    /**
     * 合并两个有序的链表，返回合并后的头节点
     * @param head1
     * @param head2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode head1, ListNode head2) {
        ListNode newNode = new ListNode(-1);//虚拟节点，数据不具备意义
        ListNode tmp = newNode ;
        while (head1 != null && head2 != null) {
            if(head1.val < head2.val) {
                tmp.next = head1;
                tmp = tmp.next;
                head1 = head1.next;
            }else {
                tmp.next = head2;
                tmp = tmp.next;
                head2 = head2.next;
            }
        }
        if(head1 != null) {
            tmp.next = head1;
        }
        if(head2 != null) {
            tmp.next = head2;
        }
        return newNode.next;
    }

    public static void main5(String[] args) {
        SingleLinkedList singleLinkedList1 = new SingleLinkedList();
        singleLinkedList1.addLast(13);
        singleLinkedList1.addLast(21);
        singleLinkedList1.addLast(32);
        singleLinkedList1.addLast(41);
        SingleLinkedList singleLinkedList2 = new SingleLinkedList();
        singleLinkedList2.addLast(15);
        singleLinkedList2.addLast(25);
        singleLinkedList2.addLast(52);
        singleLinkedList2.addLast(81);

        //ret就是新的链表的头节点
        ListNode ret = mergeTwoLists(singleLinkedList1.head,singleLinkedList2.head);
        singleLinkedList1.myToString(ret);
    }


    public static void main41(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addLast(1);
        singleLinkedList.addLast(2);
        singleLinkedList.addLast(3);
        singleLinkedList.addLast(4);
        singleLinkedList.myToString();

        ListNode ret = singleLinkedList.findKthToTail(17);
        System.out.println(ret.val);

        //singleLinkedList.reverseList();
        //singleLinkedList.myToString();
    }

    public static void main4(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addLast(1);
        singleLinkedList.addLast(1);
        singleLinkedList.addLast(1);
        singleLinkedList.addLast(1);
        singleLinkedList.myToString();

        //singleLinkedList.removeAllKey(1);
        singleLinkedList.clear();
        singleLinkedList.myToString();
        System.out.println(singleLinkedList.size());

    }

    public static void main3(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addLast(1);
        singleLinkedList.myToString();//
        singleLinkedList.remove(1);
        singleLinkedList.myToString();//
    }

    public static void main12(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addLast(1);
        singleLinkedList.addLast(2);
        singleLinkedList.addLast(3);
        singleLinkedList.addLast(4);
        singleLinkedList.myToString();
        singleLinkedList.addIndex(0,199);
        singleLinkedList.myToString();//199 1 2 3 4
        singleLinkedList.addIndex(5,299);
        singleLinkedList.myToString();//199 1 2 3 4 299
        singleLinkedList.addIndex(2,999);
        singleLinkedList.myToString();//199 1 999 2 3 4 299
        System.out.println("删除：：：：：：：");
        singleLinkedList.remove(199);
        singleLinkedList.myToString();// 1 999 2 3 4 299
        singleLinkedList.remove(299);
        singleLinkedList.myToString();// 1 999 2 3 4

        singleLinkedList.remove(999);
        singleLinkedList.myToString();// 1  2 3 4
    }

    public static void main1(String[] args) {
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.createList();
        singleLinkedList.myToString();
        System.out.println(singleLinkedList.contains(12));
        System.out.println("长度："+singleLinkedList.size2());
        System.out.println("长度："+singleLinkedList.size());
    }
}
